/*
题目：滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
 */
public class Offer59A {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return nums;
        }
        Deque<Integer> deque = new LinkedList<> ();//双端队列，保持队头是最大值
        int[] ans = new int[nums.length - k + 1];
        int index = 0;//记录ans数组下标

        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offer(i);
        }
        ans[index++] = nums[deque.peekFirst()];

        for (int i = k; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offer(i);
            while (i - deque.peekFirst() >= k) {
                deque.pollFirst();
            }
            ans[index++] = nums[deque.peekFirst()];
        }

        return ans;
    }
}
